/**
 * 给定数组A，执行如下操作：
 * i x: 每次将Ai改成x，然后回答mex(A)
 * 单点修改用树状数组，回答时在树状数组上二分即可
 * 注意0和特别大数可以单独处理
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

struct FenwickTree{ // 树状数组

using value_type = long long int;
using vec_type = vector<value_type>;

int n;
vec_type c;

FenwickTree() = default;

static int lowbit(int x){return x & -x;}

void init(int nn){this->c.assign((this->n=nn) + 1, 0);}

void modify(int pos, value_type delta){
    for(int i=pos;i<=this->n;i+=lowbit(i)) this->c[i] += delta;
}

value_type query(int pos)const{
    value_type ans = 0;
    for(int i=pos;i;i-=lowbit(i)) ans += this->c[i];
    return ans;
}

value_type query(int s, int e)const{return this->query(e) - this->query(s - 1);}

}Bt, Ct;

using vi = vector<int>;
using llt = long long;

int N, Q;
vi A, W;
vector<pair<int, int>> Questions;

inline bool check(int x){
    return Bt.query(x) == x;
}

int proc(){
    int left = 1, right = N, mid;
    do{
        mid = (left + right) >> 1;
        if(check(mid)) left = mid + 1;
        else right = mid - 1;
    }while(left <= right);
    // cout << left << " " << right << endl;
    return left;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    cin >> N >> Q;
    Bt.init(N);
    Ct.init(N);
    A.assign(N + 1, 0);
    int zero = 0;
    for(int i=1;i<=N;++i) {
        cin >> A[i];
        if(0 == A[i]) ++zero;
        else if(A[i] <= N) {
            Ct.modify(A[i], 1);
            if(0 == Bt.query(A[i], A[i])){
                Bt.modify(A[i], 1);
            }            
        }
    }

    int ans = 0;
    if(zero){
        ans = proc();
    }

    for(int k,x,i=0;i<Q;++i){
        cin >> k >> x;
        if(0 == A[k]) --zero;
        else if(A[k] <= N){
            Ct.modify(A[k], -1);
            if(0 == Ct.query(A[k], A[k])){
                Bt.modify(A[k], -1);
            }
        }

        A[k] = x;
        if(0 == x) ++zero;
        else if(x <= N){
            Ct.modify(x, 1);
            if(1 == Ct.query(x, x)){
                Bt.modify(x, 1);
            }
        }

        ans = 0;
        if(zero) ans = proc();
        cout << ans << endl;
    }
   
    return 0;
}